Skip to Content

1. 算法概述

  • 目标：给定一个序列（最典型的例子是链表），判断这个序列中是否存在环。如果存在，还能进一步找出环的入口点。
  • 核心思想：快慢指针 (Fast and Slow Pointers)。
  • 适用性：任何可以通过 next 指针或函数迭代的序列，如链表、某些函数的迭代序列等。

2. 核心思想：快慢指针

想象一个环形的跑道。如果一只乌龟和一只兔子同时从起点出发，沿着跑道同向赛跑，兔子的速度是乌龟的两倍。那么，即使乌龟先跑了一段路程，兔子也必然会在未来的某一时刻从后面追上并超过乌龟（即“套圈”）。

Floyd 判圈算法就利用了这个简单的道理：

  1. 创建两个指针：一个慢指针 slow (乌龟) 和一个快指针 fast (兔子)。
  2. 两个指针都从序列的头部开始。
  3. 在一个循环中，每次迭代：
    • slow 指针向后移动 一步 (slow = slow->next)。
    • fast 指针向后移动 两步 (fast = fast->next->next)。
  4. 根据两个指针的动向，会出现两种结果：
    • 无环：fast 指针会首先到达序列的末尾 (即 fast 或 fast->next 变为 nullptr)。这意味着兔子跑到了终点，说明跑道不是环形的。
    • 有环：fast 指针会先进入环，然后在环里一圈一圈地跑。slow 指针稍后也会进入环。一旦两个指针都在环内，fast 指针每个单位时间都会比 slow 指针多跑一步，所以 fast 最终必然会从后面追上 slow，即两个指针指向同一个节点。

3. 算法的两个阶段

Floyd 判圈算法分为两个关键阶段。

阶段一：判断是否存在环 (Cycle Detection)

这是算法的核心部分。通过移动快慢指针，判断它们是否会相遇。

  • 相遇 -> 有环：如果在 fast 到达终点前，有 slow == fast 的情况发生，那么就可以断定链表中存在环。
  • fast 到达终点 -> 无环：如果循环结束（因为 fast 或 fast->next 为 nullptr），则说明无环。

阶段二：找到环的入口 (Finding the Cycle’s Start)

这是算法精妙的延伸。当快慢指针在环内第一次相遇后，我们有办法精确地找到环的起始节点。

方法：

  1. 当 slow 和 fast 在环内相遇时，保持 slow 指针位置不变（或者 fast，无所谓）。
  2. 将另一个指针（比如，我们再创建一个新指针 ptr）重新指向链表的头部 head。
  3. 现在，让 ptr 和 slow 指针同时以相同的慢速度（每次一步）向前移动。
  4. 它们下一次相遇的节点，恰好就是环的入口节点。

为什么这个方法有效？—— 数学证明

让我们用一些变量来分析：

  • 链表头到环入口的距离为 m。
  • 环的周长为 n。
  • slow 和 fast 在环内相遇点距离环入口的距离为 k。

当它们相遇时：

  • slow 指针走过的距离 dist_slow = m + k (可能还走了几圈，但为了简化，我们先假设第一圈相遇，这不影响最终结论)
  • fast 指针走过的距离 dist_fast = m + k + c * n (c是fast比slow多跑的圈数)

因为 fast 的速度是 slow 的两倍，所以 dist_fast = 2 * dist_slow。 m + k + c * n = 2 * (m + k) m + k + c * n = 2m + 2k 整理得：m + k = c * n

这个公式非常关键！它告诉我们 m+k 的长度是环周长 n 的整数倍。 我们再把公式变形一下： m = c * n - k 这个公式可以理解为：m = (c - 1) * n + (n - k)

这个公式的几何意义是什么？

  • m: 从链表头走到环入口的距离。
  • n - k: 从相遇点继续往前走，回到环入口的距离。

所以 m = (c-1)个完整的环周长 + (从相遇点到环入口的距离)。

这意味着，如果一个指针从链表头 (head) 出发，另一个指针从相遇点 (meet) 出发，它们都以相同的速度（一步一步）前进，那么当从head出发的指针走了 m 步到达环入口时，从meet点出发的指针也恰好走了 m 步。而它走 m 步之后的位置在哪里呢？就是走了 (c-1) 圈后，又走了 n-k 步，正好也到达了环的入口！

因此，它们必然在环的入口处相遇。

4. C++ 代码实现

下面是一个完整的、可运行的 C++ 示例，实现了链表环的检测和入口查找。

#include <iostream>
#include <unordered_set>
 
// 定义链表节点
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }
 
        ListNode *slow = head;
        ListNode *fast = head;
        bool hasCycle = false;
 
        // 阶段一：判断是否有环，寻找相遇点
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
 
        // 如果没有环，直接返回 nullptr
        if (!hasCycle) {
            return nullptr;
        }
 
        // 阶段二：寻找环的入口
        // 将一个指针放回头节点，另一个保持在相遇点
        ListNode *ptr = head;
        while (ptr != slow) {
            ptr = ptr->next;
            slow = slow->next;
        }
        
        return ptr; // 它们相遇的地方就是环的入口
    }
};
 
int main() {
    // 创建一个带环的链表: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (环从3开始)
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    ListNode *cycleStart = new ListNode(3);
    head->next->next = cycleStart;
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = cycleStart; // 形成环
 
    Solution sol;
    ListNode *entry = sol.detectCycle(head);
 
    if (entry != nullptr) {
        std::cout << "Cycle detected! The cycle starts at node with value: " << entry->val << std::endl;
    } else {
        std::cout << "No cycle detected." << std::endl;
    }
 
    // 创建一个无环链表
    ListNode* noCycleHead = new ListNode(1);
    noCycleHead->next = new ListNode(2);
    noCycleHead->next->next = new ListNode(3);
 
    entry = sol.detectCycle(noCycleHead);
    if (entry != nullptr) {
        std::cout << "Cycle detected! The cycle starts at node with value: " << entry->val << std::endl;
    } else {
        std::cout << "No cycle detected in the second list." << std::endl;
    }
 
 
    // TODO: 实际应用中需要手动释放链表内存，此处为演示省略
    return 0;
}

5. 算法特性与对比

我们通常将 Floyd 判圈算法与哈希表法进行比较。

特性Floyd 判圈算法 (龟兔赛跑)哈希表法 (Hash Set)
核心思想快慢指针记录所有访问过的节点
时间复杂度O(N)，其中N是链表长度。
虽然指针会走多步，但总步数与N成线性关系。		O(N)
每个节点访问和插入哈希表一次。
空间复杂度O(1)
只使用了固定的几个指针，是原地算法。		O(N)
在最坏情况下（无环），需要存储所有节点。
优点空间效率极高。逻辑相对简单，容易理解和实现。
缺点理解背后的数学原理需要花点时间。空间开销大，不适用于内存受限的场景。

6. 应用场景

  • 链表环检测：最经典的应用。
  • 伪随机数生成器：一些简单的伪随机数生成器 (PRNG) 最终会进入一个循环，此算法可以检测出循环并找到循环节的起点和长度。
  • 函数迭代：分析函数 x = f(x) 的迭代序列 x, f(x), f(f(x)), ... 是否会陷入循环。
  • 密码学：Pollard’s rho 算法在整数分解中就使用了 Floyd 判圈的思想。
Last updated on
Map